﻿#include "DoubleLinke.h"
// C/C++ 学习网站：https://legacy.cplusplus.com 注意旧版本（搜索）和新版本

double_node* create_double_node(double_node_type n)
{ // 创建双向链表节点
    double_node* p_node = (double_node*)malloc(sizeof(double_node));
    if (p_node == NULL) {
        perror("create_double_node!\n");
        return NULL;
    }
    else {
        p_node->data = n;
        p_node->next = NULL;
        p_node->prev = NULL;
    }
    return p_node;
}

void printf_double_list(double_node* head)
{ // 打印双向链表,需要传入头结点
    if (head == NULL) {
        printf("链表为空！\n");
        return;
    }
    while (head->next != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("%d\n", head->data);
    head = NULL; // 手动释放无用指针，防止堆区指针可能退出函数时保留
}

void add_head_double_node(double_node** head, double_node_type n)
{ // 在双向链表头部添加节点
    double_node* p_node = create_double_node(n);
    if (p_node == NULL) { // 内存分配失败
        perror("add_head_double_node！\n");
        return;
    }
    else if (*head == NULL);
    else {
        p_node->next = *head;
        (*head)->prev = p_node;
    }
    *head = p_node;
    p_node = NULL;
    head = NULL; // 手动释放无用指针，栈区指针，不用释放也行
    //printf("添加头部节点成功！\n");
}

void del_head_double_node(double_node** head)
{ // 删除双向链表头部节点
    if (*head == NULL) { // 链表为空
        printf("链表为空！\n");
        return;
    }
    double_node* p_node = *head;
    *head = p_node->next;
    p_node->next = NULL;
    (*head)->prev = NULL;
    free(p_node);
    p_node = NULL;
    head = NULL; // 手动释放无用指针
    //printf("删除头部节点成功！\n");
}

void add_end_double_node(double_node** head, double_node_type n)
{ // 在双向链表尾部添加节点
    double_node* p_node = create_double_node(n);
    if (p_node == NULL) { // 内存分配失败
        perror("add_end_double_node！\n");
        return;
    }
    if (*head == NULL) // 链表为空，则头结点指向新节点
        *head = p_node;
    else {
        double_node* p_cursor = *head; // cursor 意为游标
        while (p_cursor->next != NULL)
            p_cursor = p_cursor->next;
        p_cursor->next = p_node;
        p_node->prev = p_cursor;
        //p_node->next = NULL;  // 本来就是 NULL
        p_node = NULL;
        p_cursor = NULL;
        //printf("添加尾部节点成功！\n");
    }
    head = NULL; // 手动释放无用指针
}

void del_end_double_node(double_node** head)
{ // 删除双向链表尾部节点
    if (*head == NULL) { // 链表为空
        printf("链表为空！\n");
        return;
    }
    double_node* p_cursor = *head;
    if (p_cursor->next == NULL) { // 链表只有一个节点
        *head = NULL;
        free(p_cursor);
        p_cursor = NULL;
        return;
    }
    double_node* p_next = p_cursor->next;
    while (p_next->next != NULL)
    {
        p_cursor = p_cursor->next;
        p_next = p_cursor->next;
    }
    p_cursor->next = NULL; // 可以不写，建议写上，防止堆区指针可能退出函数时保留
    p_cursor = NULL;
    //p_next->next = NULL; // 循环结束后，p_next 指向尾节点，其 next 指针本来就是 NULL
    p_next->prev = NULL; // 尾节点的 prev 指针指向前一个节点，这里置空
    free(p_next);
    p_next = NULL;
    head = NULL; // 手动释放无用指针
    //printf("删除尾部节点成功！\n");
}

size_t get_double_list_len(double_node* head)
{ // 获取双向链表长度
    if (head == NULL)
        return 0;
    size_t len = 1;
    while (head->next != NULL) {
        head = head->next;
        ++len;
    }
    head = NULL; // 手动释放无用指针
    return len;
}

void insert_double_node(double_node** head, size_t index, double_node_type n)
{ // 在双向链表指定位置插入节点
    if (index < 0 || index > get_double_list_len(*head)) { // 索引超出范围
        printf("节点位置超出范围！节点插入失败\n");
        return;
    }
    else if (index == 0) { // 插入到头部
        add_head_double_node(head, n);
        return;
    }
    else if (index == get_double_list_len(*head)) { // 插入到尾部
        add_end_double_node(head, n);
        return;
    }
    else {
        double_node* p_node = create_double_node(n);
        if (p_node == NULL) { // 内存分配失败
            perror("insert_double_node！\n");
            return;
        }
        double_node* p_cursor = *head;
        int i;
        for (i = 1; i < index; ++i)
            p_cursor = p_cursor->next; // 找到插入位置的前一个节点
        double_node* p_next = p_cursor->next; // 找到插入位置的后一个节点
        p_node->next = p_next;
        p_next->prev = p_node;
        p_node->prev = p_cursor;
        p_cursor->next = p_node;
        p_node = NULL;
        p_cursor = NULL;
        p_next = NULL;
    }
    head = NULL; // 手动释放无用指针
    //printf("在 %d 位置插入节点数据 %d 成功！\n", index, n);
}

void del_double_node(double_node** head, size_t index)
{ // 删除双向链表指定位置节点
    if (index < 1 || index > get_double_list_len(*head)) { // 索引超出范围
        printf("节点位置超出范围！节点删除失败\n");
        return;
    }
    if (index == 1) // 删除头部节点
        del_head_double_node(head);
    else if (index == get_double_list_len(*head)) // 删除尾部节点
        del_end_double_node(head);
    else {
        double_node* p_cursor = *head;
        int i;
        for (i = 1; i < index - 1; ++i)
            p_cursor = p_cursor->next;
        double_node* p_del = p_cursor->next;
        double_node* p_next = p_del->next;
        p_cursor->next = p_next;
        p_next->prev = p_cursor;
        p_del->next = NULL;
        p_del->prev = NULL;
        free(p_del);
        p_del = NULL;
        p_cursor = NULL;
        p_next = NULL;
    }
    head = NULL; // 手动释放无用指针
    //printf("删除 %d 位置节点成功！\n", index);
}

int del_num_double_list(double_node** head, double_node_type num)
{ // 删除双向链表中的一个数据，返回其位置
    if (head == NULL) {
        printf("链表为空！\n");
        return -1; // 链表为空
    }
    double_node* p_cursor = *head;
    if ((*head)->data == num) // 链表头结点就是要删除的数据
    {
        (*head) = (*head)->next;
        (*head)->prev = NULL;
        p_cursor->next = NULL;
        free(p_cursor);
        p_cursor = NULL;
        return 1;
    }
    int index = 1;
    double_node* p_prev = p_cursor;
    while (p_cursor->next != NULL)
    {
        p_cursor = p_cursor->next;
        ++index;
        if (p_cursor->data == num)
        {
            if (p_cursor->next == NULL) // 要删除的节点是尾节点           
                p_prev->next = NULL;
            else { // 要删除的节点不是尾节点
                double_node* p_next = p_cursor->next; // 找到要删除的数据的下一个节点
                p_prev->next = p_next; // 前一个节点的 next 指向当前节点的下一个节点
                p_next->prev = p_prev; // 当前节点的下一个节点的 prev 指向前一个节点
                p_cursor->next = NULL; // 当前节点的 next 指针指向 NULL
                p_next = NULL; // 手动释放无用指针
            }
            p_cursor->prev = NULL; // 当前节点的 prev 指针指向 NULL
            free(p_cursor); // 释放当前节点内存
            p_cursor = NULL; // 手动释放无用指针
            p_prev = NULL; // 手动释放无用指针
            //printf("在 %d 位置删除数据 %d\n", index, num);              
            return index;
        }
        else
            p_prev = p_prev->next; // p_del 指向前一个节点
    }
    printf("没有找到数据 %d\n", num);
    head = NULL; // 手动释放无用指针
    p_prev = NULL; // 手动释放无用指针
    return -1; // 没有找到数据
}

void reverse_double_list1(double_node** head)
{ // 反转双向链表，这里使用迭代方式，循环交换节点 next 和 prev 指针
    if (*head == NULL) // 链表为空
        return;
    double_node* p_cursor = *head; // 游标节点
    double_node* p_next = p_cursor->next; // 保存下一个节点
    struct DoubleNode* temp;
    while (p_cursor->next != NULL)
    {
        temp = p_cursor->next; // 保存下一个节点
        p_cursor->next = p_cursor->prev; // 连接前一个节点
        p_cursor->prev = temp; // 连接后一个节点
        p_cursor = p_next; // 后移游标节点
        p_next = p_cursor->next; // 后移下一个节点
    }
    p_cursor->next = p_cursor->prev; // 最后一个节点是首节点，再次连接
    p_cursor->prev = NULL; // 循环结束后，最后一个节点是第一个节点 prev 指针指向 NULL
    *head = p_cursor; // 头结点指向最后一个节点
    p_cursor = NULL; // 手动释放无用指针
    p_next = NULL; // 手动释放无用指针
    temp = NULL; // 无用指针
    //printf("反转双向链表成功！\n");
}

double_node* reverse_double_list2(double_node* head)
{ // 反转双向链表，这里使用递归方式
    if (head->next == NULL) { // 链表只有一个节点
        head->prev = NULL; // 只有一个节点，prev 指针指向 NULL
        return head;
    }
    double_node* new_head = reverse_double_list2(head->next);
    // 递归调用，保存最后一个节点
    double_node* prev = head->next; // 保存当前节点的递归返回节点（下一个节点）
    prev->next = head; // 将下一个节点连接到当前节点
    head->prev = prev; // 连接当前节点的 prev 指针到 prev 节点
    //((head->next)->next) = head; // 写成这样编译不过去
    head->next = NULL; // 连接完成后，当前节点是尾节点，需要将 next 指针指向 NULL
    return new_head; // 递归返回新链表的头结点（旧链表的尾结点）
}

int search_num_double_list(double_node* head, double_node_type num)
{ // 在双向链表中查找一个数据，返回其位置
    if (head == NULL) {
        printf("链表为空！\n");
        return -1; // 链表为空
    }
    int index = 1;
    while (head->next != NULL)
    {
        if (head->data == num)
        {
            printf("在 %d 位置找到数据 %d\n", index, num);
            return index;
        }
        head = head->next;
        ++index;
    }
    printf("没有找到数据 %d\n", num);
    head = NULL; // 手动释放无用指针
    return -1; // 没有找到数据
}

double_node* dli1_add_dli2(double_node* head1, double_node* head2)
{ // 将 head2 链表追加到 head1 链表的尾部，返回合并后的链表头结点
    if (head1 == NULL) // 链表1为空
        return head2;
    else if (head2 == NULL) // 链表2为空
        return head1;
    double_node* p_cursor1 = head1;
    while (p_cursor1->next != NULL)
        p_cursor1 = p_cursor1->next;
    p_cursor1->next = head2;
    head2->prev = p_cursor1; // 连接链表 2 的尾节点到链表 1 的尾节点
    p_cursor1 = NULL; // 手动释放无用指针
    //printf("链表合并成功！\n");
    return head1; // 这里返回 head1 即可，因为 head1 已经是合并后的链表头结点
}

/*static void swap_double_node(double_node* p_node1, double_node* p_node2)
{ // 交换两个节点的数据
    double_node_type temp = p_node1->data;
    p_node1->data = p_node2->data;
    p_node2->data = temp;
} */

void print_front_and_end(double_node* head)
{ // 打印双向链表的前后节点数据
    if (head == NULL) {
        printf("链表为空！\n");
        return;
    }
    size_t len = 1;
    while (head != NULL)
    {
        double_node* p_prev = head->prev;
        double_node* p_next = head->next;
        if (head->prev == NULL) {
            printf("first->prev is NULL\n");
            printf("first->next->data = %d\n", p_next->data);
        }
        else if (head->next == NULL) {
            printf("last->prev->data = %d\n", p_prev->data);
            printf("last->next is NULL\n");
        }
        else
            printf("node_%zd->prev->data = %d, node_%zd->next->data = %d\n",
                len, p_prev->data, len, p_next->data);
        head = head->next;
        ++len;
    }
}

void insertion_sort_doubly_linke(double_node* head)
{ // 排序双向链表，插入排序算法
    if (head == NULL || head->next == NULL) // 链表为空或只有一个节点
        return;
    double_node* p_cursor = head->next; // 第一个节点
    double_node* p_prev = NULL; // 前驱节点
    double_node* p_prev_prev = NULL; // 前前驱节点
    double_node_type temp;
    while (p_cursor != NULL)
    {
        p_prev = p_cursor;
        p_prev_prev = p_prev->prev;
        while (p_prev_prev)
        {
            if (p_prev_prev->data > p_prev->data) // 找到插入位置
            {
                temp = p_prev->data;
                p_prev->data = p_prev_prev->data;
                p_prev_prev->data = temp;
            }
            p_prev = p_prev_prev;
            p_prev_prev = p_prev_prev->prev;
        }
        p_cursor = p_cursor->next;
    }
    p_prev = NULL; // 手动释放无用指针
    head = NULL; // 手动释放无用指针
    //printf("排序双向链表成功！\n");
}

double_node* last_node(double_node* head) {
    while (head && head->next) {
        head = head->next;
    }
    return head;
}

// 交换节点数据快速排序的分区函数
static double_node* partition(double_node* low, double_node* high) {
    double_node_type pivot = high->data;
    double_node* i = low; // 修改初始值为 low，而不是 NULL
    for (double_node* j = low; j != high; j = j->next) {
        if (j->data <= pivot) {
            int temp = i->data;
            i->data = j->data;
            j->data = temp;
            i = i->next;
        }
    }
    int temp = i->data;
    i->data = high->data;
    high->data = temp;
    return i;
}

// 以下是快速排序交换节点数据算法递归函数的实现
static void _quick_sort(double_node* low, double_node* high) {
    if (high != NULL && low != high && low != high->next) {
        double_node* p = partition(low, high);
        _quick_sort(low, p->prev);
        _quick_sort(p->next, high);
    }
}

void quick_sort_doubly_linked(double_node* head) {
    double_node* last = last_node(head);
    _quick_sort(head, last);
}

void destroy_double_list(double_node* head)
{ // 释放双向链表内存，双向链表的储存可能不是连续的，需要逐个释放
    double_node* p_del;
    while (head->next != NULL)
    {
        p_del = head;
        head = head->next;
        p_del->next = NULL;
        free(p_del);
        p_del = NULL;
    }
    free(head);
    head = NULL;
    printf("释放双向链表内存成功！\n");
}
